package org.example.myleet.p720;

import java.util.Arrays;
import java.util.Comparator;
import java.util.HashSet;

public class Solution {

//    public String longestWord(String[] words) {
//        String candidate = "";
//        Arrays.sort(words, Comparator.comparingInt(String::length));
//        HashSet<String> set = new HashSet<>(words.length);
//        for (String word : words) {
//            if (word.length() == 1 || set.contains(word.substring(0, word.length() - 1))) {
//                set.add(word);
//                if (candidate.length() < word.length()) {
//                    candidate = word;
//                } else if (candidate.length() == word.length()) {
//                    if (candidate.compareTo(word) > 0) {
//                        candidate = word;
//                    }
//                }
//            }
//        }
//        return candidate;
//    }

    private static final int CHARSET_SIZE = 26;

    public String longestWord(String[] words) {
        String candidate = "";
        Arrays.sort(words, Comparator.comparingInt(String::length));
        TrieTree trieTree = new TrieTree();
        for (String word : words) {
            if (word.length() == 1 || trieTree.isWordExist(word.substring(0, word.length() - 1).toCharArray())) {
                trieTree.addWord(word.toCharArray());
                if (candidate.length() < word.length()) {
                    candidate = word;
                } else if (candidate.length() == word.length()) {
                    if (candidate.compareTo(word) > 0) {
                        candidate = word;
                    }
                }
            }
        }
        trieTree.clear(trieTree.getRoot());
        return candidate;
    }

    static class TrieTree {
        TrieNode root;

        public TrieTree() {
            root = new TrieNode();
        }

        public TrieNode getRoot() {
            return root;
        }

        public void addWord(char[] word) {
            TrieNode node = root;
            for (int i = 0; i < word.length; ++i) {
                TrieNode child = node.children[word[i] - 'a'];
                if (null == child) {
                    child = new TrieNode();
                    node.children[word[i] - 'a'] = child;
                }
                node = child;
            }
            node.end = true;
        }

        public boolean isWordExist(char[] word) {
            TrieNode node = root;
            for (int i = 0; i < word.length; ++i) {
                TrieNode child = node.children[word[i] - 'a'];
                if (null == child) {
                    return false;
                }
                node = child;
            }
            if (null == node) {
                return false;
            }
            return node.end;
        }

        public void clear(TrieNode node) {
            for (int i = 0; i < CHARSET_SIZE; ++i) {
                if (null != node.children[i]) {
                    clear(node.children[i]);
                }
                node.children[i] = null;
            }
        }
    }

    static class TrieNode {
        TrieNode[] children;
        boolean end;

        public TrieNode() {
            children = new TrieNode[CHARSET_SIZE];
            end = false;
        }
    }
}
